package primary.code07_Greedy;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 切黄金，每次切割的费用为切割前的长度
 *
 * @author Yudi Wang
 * @date 2021/8/4 11:09
 */
public class Code02_cutGold {

    /**
     * 返回切割的最小费用
     *
     * @param cutted 切割后的每段长度
     * @return
     */
    public static int minCost(Integer[] cutted) {
        int cost = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (Integer integer : cutted) {
            queue.add(integer);
        }
        while (queue.size() != 1) {
            Integer o1 = queue.poll();
            Integer o2 = queue.poll();
            Integer lengthBefore = o1 + o2;
            cost += lengthBefore;
            queue.add(lengthBefore);
        }
        return cost;
    }

    public static int minCostTest(Integer[] cutted) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.addAll(Arrays.asList(cutted));
        int res = 0;
        while (heap.size() > 1) {
            int l1 = heap.poll();
            int l2 = heap.poll();
            res += (l1 + l2);
            heap.add(l1 + l2);
        }
        return res;
    }

    public static void main(String[] args) {
        Integer[] cutted = {3, 3, 4, 5, 7, 8, 10, 12};
        System.out.println("黄金切割最小费用1：" + minCost(cutted));
        System.out.println("黄金切割最小费用2：" + minCostTest(cutted));
    }
}
